Clone Graph
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're maintaining a web of contacts. Every contact has a unique id and a list of the other contacts it's directly linked with (a link always goes both ways).
You're handed one contact from this web. Build a completely separate copy of every contact reachable from it, using brand new contact objects, so that the same ids are linked together the same way. Editing your copy must never affect the original web, and the copy must not reuse a single object from it.
Input: web = {1: [2], 2: [1]}, start = 1
Output: an independent web shaped like {1: [2], 2: [1]}
Two contacts linked to each other. Your copy has two brand new contact objects, still linked to each other the same way.
Input: web = {1: [2, 3], 2: [1, 3], 3: [1, 2]}, start = 1
Output: an independent web shaped like the original, starting from a copy of contact 1
Three contacts all linked to each other. Notice that following the links from contact 1 eventually leads back to contact 1, so your traversal has to avoid looping forever.
Input: web = {1: []}, start = 1
Output: a single, separate contact with no links
A contact with no links still needs its own fresh copy.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.